// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-03-02 17:35
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

public class RemoveKDigits {
    // 一处数字使得剩下的数字最小
    // 遍历比较-> 朴素删除
    // 单调栈 -> 使得栈内元素尽可能小-> 保持高位数值尽可能小
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (n <= k) {
            return "0";
        }
        int remain = n - k;
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char digit = num.charAt(i);
            while (builder.length() > 0 && builder.charAt(builder.length() - 1) > digit && k > 0) { // 新来的元素小于栈顶元素，并且可以删除数字;while循环的目的是实现栈内元素最小化
                int len = builder.length();
                if (builder.charAt(len - 1) != '0') { // 如果栈顶元素是0则不需要消耗修改次数
                    k--;
                }
                builder.deleteCharAt(len - 1);
            }

            builder.append(digit);
        }
        if (builder.length() > remain) {
            // 字符串过长
            builder.delete(remain, builder.length());
        }
        while (builder.length() > 1 && builder.charAt(0) == '0') {
            builder.deleteCharAt(0);
        }

        return builder.length() == 0 ? "0" : builder.toString();
    }

    @Test
    public void shout00() {
        String num = "1022";
        int k = 2;
        System.out.println(removeKdigits(num, k));
    }


}
